package com.hejjon;

import java.util.Objects;

/**
 * 14. 最长公共前缀
 * https://leetcode.cn/problems/longest-common-prefix/
 *
 * @author: caoshi
 * @date: 2023-01-27 09:36:48
 * @since: 1.0
 */
public class LongestCommonPrefix {


    public static void main(String[] args) {

//        String[] strs = new String[]{"flower", "flow", "floiwght"};
        String[] strs = new String[]{"dog","racecar","car"};

        String ans = longestCommonPrefix2(strs);
        System.out.println(ans);
    }

    /**
     *  先找到长度最短的字符串
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        StringBuilder ansb = new StringBuilder();
        // 找到最短的字符串
        int minLen = strs[0].length();
        String minStr = strs[0];
        int minStrIndex = 0;
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].length() < minLen) {
                minLen = strs[i].length();
                minStr = strs[i];
                minStrIndex = i;
            }
        }

        for (int i = 0; i < minStr.length(); i++) {
            char ch = minStr.charAt(i);
            boolean comm = true;
            for (int j = 0; j < strs.length; j++) {
                if (j != minStrIndex) {
                    String str = strs[j];
                    if (!Objects.equals(ch, str.charAt(i))) {
                        comm = false;
                        break;
                    }
                }
            }
            if (comm) {
                ansb.append(ch);
            } else {
                return ansb.toString();
            }
        }
        return ansb.toString();
    }

    /**
     *  使用 字符串截取方法
     * @param strs
     * @return
     */
    public static String longestCommonPrefix2(String[] strs) {
        String ans = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            for (; j < strs[i].length() && j < ans.length(); j++) {
                if (ans.charAt(j) != strs[i].charAt(j)) {
                    break;
                }
            }
            ans = strs[i].substring(0, j);
        }

        return ans;
    }


}
